package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * @author feizns
 * @since 2020/3/9
 */
public class BuildTree {

    int pL;

    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        return buildTree(preOrder, inOrder, 0, inOrder.length - 1);
    }

    private TreeNode buildTree(int[] preOrder, int[] inOrder, int l, int r) {
        if ( l <= r ) {
            TreeNode root = new TreeNode(preOrder[pL++]);
            int i = l;
            for (; i <= r && inOrder[i] != root.val; i++) { }
            root.left = buildTree(preOrder, inOrder, l, i - 1);
            root.right = buildTree(preOrder, inOrder, i + 1, r);
            return root;
        }
        return null;
    }

}
